1. Field of Invention
The present invention is related to iterative decoding of LDPC codes represented by finite-length graphs. Specifically, the invention deals with low-complexity quantized decoders for LDPC codes that have potential to outperform the floating-point BP decoder on a finite-length graph.
2. Description of the Related Art
Error-correcting codes are indispensable for any modern digital communication system which requires reliable transmission and/or storage of digital data. A class of error-correcting codes called low-density parity-check (LDPC) codes, that were originally discovered by Gallager in the 1960's and rediscovered some thirty years later, have sparked a widespread interest in the field of coding theory. These codes are based on the principle of iterative decoding (or message-passing) and were shown to asymptotically perform close to the theoretical limit established by Shannon's noisy channel coding theorem. The standard BP decoder or modified versions of it are mostly commonly used for decoding LDPC codes and carried out on the graph representations of the code. The remarkable performance of LDPC codes as well as their simple and efficient high-speed implementations have made them very attractive for use in a plethora of applications ranging from wireless communication and deep-space communication systems to magnetic storage media.
In the past few years, a considerable amount of research has been dedicated towards constructing LDPC codes that have good distance properties, and finding better iterative decoders that enable simpler hardware implementations as well as have good asymptotic performance. Richardson et. al. in proposed the technique of density evolution under BP decoding in order to determine the asymptotic decoding threshold of a particular code and suggested using this analysis in order to optimize the code's profile for the best possible decoding threshold. Although the density evolution approach can provide a fairly accurate prediction of the performance of a code in the very low signal-to-noise ration (SNR) region (or waterfall region), it cannot predict in the higher SNR region (or error floor region). This can be attributed to the fact that the density evolution approach does not take into account the finite-length effects of the code since it assumes an infinite code length and the variable node considers the graph representation of the code to be a tree. Therefore, BP decoding is suboptimal for practical implementations of LDPC codes. It was also observed by MacKay et. al. in that certain LDPC codes that had a fairly good minimum distance exhibited relatively high error floors in their performance. Error floor is an undesirable phenomenon of iterative codes in general, that is said to have occurred when the performance curve of a given code flattens out thus exhibiting an almost fixed error rate even at high SNR. MacKay et. al. attributed this phenomenon to certain potentially harmful structures in the graph representation of the LDPC code called near-code words, and later Richardson formally introduced them in as trapping sets where the decoder failed to converge to a codeword for certain low-weight error patterns. These trapping sets can be present in any finite-length code even though it has been optimized for a good decoding threshold. Hence, LDPC codes that are optimized using the density evolution approach can still exhibit high error floors.
The class of quantized decoders, where only a fixed number of bits are allowed for representation of the messages, are also important to address when considering practical implementations due to hardware limitations. Some properties that are typically desirable for quantized decoders are simpler hardware implementations and minimal degradation in performance compared to the floating-point BP decoder. The prior art uses a quantized BP decoder with a quantization scheme that considerably simplifies the processing at the check node. The prior art also uses a quantization unit that determines a quantization width based on density evolution. Other works related to modifications of BP decoding for simpler implementations and use of the density evolution approach to find good quantized decoders can also be found in the literature. It must be noted that in all these works, there is still some degradation in the performance of quantized decoders compared to the floating-point BP decoder on finite-length graphs. The same issues also exist in inventions in the current state of the art for quantized decoders. Also for reasons mentioned in the previous paragraph, the loss can become even more significant when the code length is relatively small and the graph of the code is relatively dense. In essence, decoders obtained via the density evolution approach cannot guarantee good performance in the higher SNR region for a finite-length code.
There are notably two ways to deal with degradation of performance in the error floor region for an LDPC code. One way is to construct codes by avoiding certain trapping sets thereby increasing the guaranteed error-correction capability of the codes and improving the performance. The other way is to improve the iterative decoding process on a finite-length graph. The first approach has been extensively studied. However, it may not always be possible to avoid certain trapping sets during construction due to limitations established by the length of the code especially when considering short length codes with relatively higher code rates. The current invention closely follows the second approach with the added constraint of finite precision for representation of messages.
LDPC codes are linear codes that are characterized by a sparse parity check matrix H containing a small number of nonzero entries. These codes can be conveniently represented by bipartite graphs called Tanner graphs, which are more useful representations when carrying out the iterative decoding process. The Tanner graph representation of an LDPC code includes two sets of nodes. One set of nodes are called variable nodes and they represent the bits associated with a codeword. The other set of nodes are called check nodes and they represent parity check constraints on the bits of the codeword which are defined by the parity check matrix H. An edge of the graph connects a variable node to a check node only if that particular bit represented by the variable node participates in the parity check equation represented by the check node. The number of nonzero entries in a column of parity check matrix determine the degree of a particular variable node and the number of nonzero entries in a row determine the degree of a check node. Regular LDPC codes are codes for which all the variable nodes have the same degree and all check nodes have the same degree, whereas irregular LDPC codes can have different degrees for different nodes. Regular LDPC codes are typically denoted as (dv, dc) codes, where dv is the degree of a variable node and dc is the degree of a check node. FIG. 1 shows the example of a tanner graph for a rate-half (3, 6) binary LDPC code with code length 8, and its corresponding parity check matrix.
The circles on the Tanner graph denote variable nodes and the boxes denote check nodes. The vector x includes bits b1 to b8 that are associated to their corresponding variable nodes v1 to v8 on the Tanner graph. x is a codeword if and only if it satisfies the matrix product, HxT=0 (satisfiability condition). This implies that every row of the parity check matrix H corresponds to a parity check constraint on the bits of a codeword. For example, the check node c1 on the Tanner graph represents the parity check equation corresponding to the first row of the parity check matrix, and the bits associated to the neighboring variable nodes v1, v2, v3, v4, v5, and v7, are involved in the parity check equation. This means that the bits associated to these variable nodes must satisfy the parity check equation b1+b2+b3+b4+b5+b7=0 (mod 2). In general, all the bits represented by the variable nodes that are connected to a particular check node must add up to zero modulo 2, and under such condition, the check node is considered to be satisfied. If the parity check equation does not hold, then the check node is considered to be unsatisfied.
For a given message vector m, the encoding process of LDPC codes can be done by deriving the generator G from H using the method of Gaussian elimination and performing the matrix multiplication mG. For decoding of LDPC codes, a message-passing algorithm is carried out on the Tanner graph of the code and messages are iteratively passed between variable nodes and check nodes along the edges of the graph. FIG. 2 illustrates the entire coding process which involves encoding a given message vector m, modulating the binary data, transmitting it across the channel which introduces errors, demodulating the signal, and then performing decoding on the received message to recover the original data.
Several message-passing algorithms exist in the state of art that are used for decoding LDPC codes. Simple low-complexity algorithms such as Gallager-A and Gallager-B algorithms utilize only hard information from the channel, i.e., the decoder receives only binary data from the channel as its input and a single bit is used to represent messages. These can be regarded as 1-bit decoders. Whereas more complex algorithms such as the BP algorithm utilize soft information from the channel where floating-point values are used to represent messages. As mentioned in the previous section, there are many modified versions of the BP decoder that have been suggested in the literature in order to simplify the decoding operations for hardware implementation, as well as quantized versions of BP decoding that use a fixed number of bits to represent the soft values. The Gallager-B and the BP algorithms are briefly described in order to make note of the distinction between multilevel decoders defined in this invention and existing state of the art decoders, since most of the existing message-passing decoders in the state of the art are related to these traditional message-passing algorithms.
Any message-passing algorithm for LDPC codes can be described by defining an update rule at the variable node and an update rule at the check node. The variable node update rule and the check node update rule can be denoted as functions ψv and ψc respectively, that are used to determine the outgoing messages. Initially, every variable node vi calculates its channel value yi based on the observation value ri that is received from the channel. For the Gallager-B algorithm the channel value yi is simply ri which is a single binary bit received from the channel in the case of the binary symmetric channel (BSC), and the value yi is simply the sign of ri in the case of other channels such as additive white Gaussian noise (AWGN) channel. For the BP algorithm implemented in the “log-likelihood domain”, the channel value y is a log-likelihood ration calculated from the observation ri. Assuming that a transmitted bit bi can be a zero or one with equal probability the value yi can be calculated as
  log  ⁢            p      ⁢              (                                            r              i                        ❘                          b              i                                =          0                )                    p      ⁡              (                                            r              i                        ❘                          b              i                                =          1                )            Where p(ri|bi=a) is simply the probability of receiving observation value ri conditioned on the transmitted bit bi being the value of a. The calculation of yi depends on the type of channel and noise distribution.
Initially, all messages are set to zero and the variable node vi receives only the channel value yi. The variable node vi simply sends this channel value yi as its outgoing message to all its neighboring check nodes in the first iteration. At the check nodes, the check node update rule ψc is used to determine the outgoing messages and the messages are passed to the variable nodes. At the variable node, the variable node update rule ψv is used to determine the outgoing messages, and in this manner messages are iteratively passed between variable nodes and the check nodes. Note that while determining the outgoing message on any particular edge of a variable or check node, the message on that particular edge is not included in the computation of the outgoing message. For example, if an outgoing message is being calculated on a particular edge of a node vi whose degree is dv, then the number of incoming messages used in the function ψv during computation is dv−1. This is to ensure the message is an extrinsic message and the dependencies between the messages entering the node are reduced. Computing the extrinsic message during an update at a particular node is a general principle that must be adhered to for any kind of message-passing decoder. For the Gallager-B algorithm, the variable node update and check node update rules are defined as
            ψ      v        ⁡          (                        y          i                ,                  m          1                ,        …        ⁢                                  ,                  m                                    d              v                        -            1                              )        =      {                                                                      1                ,                                                                                      if                  ⁢                                                                          ⁢                  the                  ⁢                                                                          ⁢                  number                  ⁢                                                                          ⁢                  of                  ⁢                                                                          ⁢                  incoming                  ⁢                                                                          ⁢                  messages                  ⁢                                                                          ⁢                  that                  ⁢                                                                          ⁢                  are                  ⁢                                                                          ⁢                  one                                ≥                                  b                                      1                    ,                                          d                      v                                                                                                                                              0                ,                                                                                      if                  ⁢                                                                          ⁢                  the                  ⁢                                                                          ⁢                  number                  ⁢                                                                          ⁢                  of                  ⁢                                                                          ⁢                  incoming                  ⁢                                                                          ⁢                  messages                  ⁢                                                                          ⁢                  that                  ⁢                                                                          ⁢                  are                  ⁢                                                                          ⁢                  zero                                ≥                                  b                                      1                    ,                                          d                      v                                                                                                                                                                y                  i                                ,                                                    otherwise                                      ⁢                                  ⁢                                  ⁢                              ψ            c                    ⁡                      (                                          m                1                            ,                              m                2                            ,              …              ⁢                                                          ,                              m                                  dc                  -                  1                                                      )                              =                        (                                    ∑                              i                =                2                                                              d                  c                                -                1                                      ⁢                          m              i                                )                ⁢        mod        ⁢                                  ⁢        2            The value bl, dv is a threshold value used in update rule of variable node vi with degree dv during the lth iteration of the decoding process. The threshold can change from iteration to iteration but is typically chosen to be a majority value for practical implementations. The Gallager-A algorithm is special instance of Gallager-B where bl, dv=dv−1. For column-weight three LDPC codes, both algorithms are equivalent. For the BP algorithm, the variable node update and check node update rules are defined as
                    ψ        v            ⁡              (                              y            i                    ,                      m            1                    ,                      m            2                    ,          …          ⁢                                          ,                      m                          dv              -              1                                      )              =          (                                    ∑                          j              =              1                                                      d                v                            -              1                                ⁢                      m            j                          +                  y          i                    )                          ψ        c            ⁡              (                              m            1                    ,                      m            2                    ,          …          ⁢                                          ,                      m                          dc              -              1                                      )              =          2      ⁢                        tanh                      -            1                          (                              ∏                          j              =              1                                                      d                c                            -              1                                ⁢                      tanh            ⁡                          (                                                m                  j                                2                            )                                      )            In the definitions, the symbol
  ∑      j    =    1              d      v        -    1  denotes the sum operator used to add up to dv−1 terms and the symbol
  ∏      j    =    1              d      c        -    1  denotes the product operator used to determine the product of dc−1 terms indexed by j. These symbols are reused throughout the specification as required.
At the end of each iteration in the decoding process, a hard decision rule is carried out at the variable node which determines whether the bit bi associated to the node vi is a one or a zero based on the values of the incoming messages and the channel value yi. For the Gallager-B algorithm bit bi is decided by comparing the number of ones and zeros to a set threshold in a similar fashion to the variable node update rule. For the BP algorithm the bit bi is decided by taking the sum of all the incoming messages to the variable node and the channel value, and observing the sign of the result. Assuming that the modulation scheme uses the typically binary map 0→1 and 1→−1, a positive sign indicates the bi to be zero and a negative sign indicates the bit bi to be one. These bits obtained from the hard decision rule are then sent to the check nodes along the edges of the graph in order to verify if all the check nodes are satisfied. If all check nodes are satisfied, the decoder has converged to a codeword and the iterative process is terminated. Else the decoder has failed to converge and the iterative process is continued until a maximum number of iterations is reached. In practice, note that performing the hard decision rule is essential only after the maximum number of iterations has been reached. Some implementations of state of art decoders prefer running the decoder for a given number of iterations all the time and performing the hard decision at the end of the decoding process without checking if the decoded output is a codeword or not. However, performing the decision rule after every iteration can increase the speed of the decoder significantly since the algorithm starts to converge much more quickly as the SNR increases and the average number of iterations required for convergence will be much lesser compared to the maximum number of iterations. Also knowledge on whether the decoder failed or not can be useful to exploit when considering using multiple decoders to correct certain error patterns as shall be expounded in the detailed description of the current invention. The concept of trapping sets is now described since they remain central to our method used to obtain the multilevel decoders in the invention. Henceforth for convenience, the bits represented by the variable nodes are referred to as the nodes themselves.
Trapping sets are small subgraphs present in the Tanner graph of the code that cause the decoder to fail for certain noise configurations or low-weight error patterns. Following the definition given by Richardson, given a decoder, a trapping set is defined as a subgraph induced by the set of variable nodes that eventually failed to decode to the right bits for a particular decoder input. In other words, these trapping sets are subgraphs containing variable nodes that either remain trapped to the wrong value or oscillate between the right and wrong value due to a specific noise configuration on the Tanner graph. The decoder failure on the subgraph is instigated by certain variable nodes in the Tanner graph that initially received bad (or extremely wrong) values from the channel due to a particularly bad noise configuration. Typically in the high SNR region, the number of variable nodes initially receiving bad channel values is quite small thus contributing to the error floor phenomenon. A particular subgraph can potentially be a trapping set depending on the channel, decoder input and the decoder itself.
For symmetric decoders and output-symmetric memoryless channels, the all-zero codeword can be assumed to be transmitted in order to simplify analysis on trapping sets. However, for asymmetric channels, and channels with memory such as magnetic recording channels, all code words must be used for analysis. A popular notation used to describe trapping sets is the (a,b) notation where a denotes the number of variable nodes in the induced subgraph and b denotes the number of odd-degree check nodes present in the induced subgraph. As an example, FIG. 3 shows how the Gallager-A algorithm fails on the (5,3) trapping set for the BSC. The variable nodes v1, v2 and v3 are initially in error (they are all ones) and the variable nodes v4 and v5 are initially correct (they are both zeros). The arrows indicate a one being transmitted from one node to the other. FIG. 3(a) illustrates the message passing from variable node to check node in the first half of iteration one. The nodes v1, v2 and v3 transmit a 1 on all its edges to the check nodes c1, . . . , c9. In the second half of iteration one, nodes v4 and v5 receive a 1 on all its edges as shown in FIG. 3(b). In the first half of iteration two, due to the variable node update rule for Gallager-A, nodes v4 and v5 send a 1 on all its edges as shown in FIG. 3(c). Finally at the end of iteration two, nodes v1, v2 and v3 receive two 1's and one 0 as shown in FIG. 3(d) and the process repeats itself in the next iteration thus resulting in a decoder failure. For the BP algorithm, the trapping sets typically contain many short cycles that are interconnected to each other in the subgraph and this causes the message-passing process of the BP algorithm to be faulty leading to decoder failure. This can cause considerable degradation in frame error rate (FER) performance of the code in the high SNR region even though the code may have a fairly good minimum distance and good decoding threshold. The codeword error rate or frame error rate gives us a measure of how likely an estimated/received codeword (or frame) will be in error and this is typically a function of SNR. Note that even if a single bit in the codeword is erroneous, the whole codeword is considered to be erroneous. The main goal of any code or decoder is to lower the FER as much as possible. As previously mentioned in the background, even codes with good properties such as good minimum distance can exhibit a high error floor due to presence of trapping sets in the finite-length graph. Therefore, improving the decoding by reducing failure rates on trapping sets is a key strategy in improving the performance in the error floor region.